/*-------------------------------------------------------------------------
 *
 * pathkeys.c
 *	  匹配和构建路径键的工具
 *
 * 有关路径键的性质和使用，请参见 src/backend/optimizer/README。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/path/pathkeys.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/stratnum.h"
#include "catalog/pg_opfamily.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "partitioning/partbounds.h"
#include "utils/lsyscache.h"


static bool fc_pathkey_is_redundant(PathKey *fc_new_pathkey, List *fc_pathkeys);
static bool fc_matches_boolean_partition_clause(RestrictInfo *fc_rinfo,
											 RelOptInfo *fc_partrel,
											 int fc_partkeycol);
static Var *fc_find_var_for_subquery_tle(RelOptInfo *fc_rel, TargetEntry *fc_tle);
static bool fc_right_merge_direction(PlannerInfo *fc_root, PathKey *fc_pathkey);


/****************************************************************************
 *		路径键构造和冗余测试
 ****************************************************************************/

/*
 * make_canonical_pathkey
 *	  给定 PathKey 的参数，在查询的“标准”路径键列表中查找任何已存在的匹配
 *	  路径键。如果还没有则创建一个新的条目。
 *
 * 注意，这个函数必须在完成合并等价类后使用。
 */
PathKey *
make_canonical_pathkey(PlannerInfo *fc_root,
					   EquivalenceClass *fc_eclass, Oid fc_opfamily,
					   int fc_strategy, bool fc_nulls_first)
{
	PathKey    *fc_pk;
	ListCell   *fc_lc;
	MemoryContext fc_oldcontext;

	/* 如果等价类的集合可能仍会改变，则无法创建标准路径键 */
	if (!fc_root->ec_merging_done)
		elog(ERROR, "too soon to build canonical pathkeys");

	/* 传入的 eclass 可能是非标准的，因此追溯到顶层 */
	while (fc_eclass->ec_merged)
		fc_eclass = fc_eclass->ec_merged;

	foreach(fc_lc, fc_root->canon_pathkeys)
	{
		fc_pk = (PathKey *) lfirst(fc_lc);
		if (fc_eclass == fc_pk->pk_eclass &&
			fc_opfamily == fc_pk->pk_opfamily &&
			fc_strategy == fc_pk->pk_strategy &&
			fc_nulls_first == fc_pk->pk_nulls_first)
			return fc_pk;
	}

	/*
	 * 确保在主要规划上下文中分配标准路径键。
	 * 在正常规划中这不是问题，但在 GEQO 中是一个问题。
	 */
	fc_oldcontext = MemoryContextSwitchTo(fc_root->planner_cxt);

	fc_pk = makeNode(PathKey);
	fc_pk->pk_eclass = fc_eclass;
	fc_pk->pk_opfamily = fc_opfamily;
	fc_pk->pk_strategy = fc_strategy;
	fc_pk->pk_nulls_first = fc_nulls_first;

	fc_root->canon_pathkeys = lappend(fc_root->canon_pathkeys, fc_pk);

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_pk;
}


/*
 * pathkey_is_redundant
 *	   一个路径键是否与给定列表中已有的路径键冗余？
 *
 * 我们检测两种情况：
 *
 * 1. 如果新的路径键的等价类包含一个常量，并且不在外连接之下，那么我们可以将其视为一个排序键而忽略它。例子：
 *			SELECT ... WHERE x = 42 ORDER BY x, y;
 * 我们完全可以只按 y 排序。请注意，由于运算符族匹配，这是语义上正确的：我们知道这个相等约束实际上将变量绑定到任何可能与等价类中的排序运算符一起使用的单一值。这个规则不仅让我们简化（甚至跳过）显式排序，还允许在存在不关心索引列的情况下将索引排序顺序与查询匹配。
 *
 * 2. 如果新的路径键的等价类与路径键列表中任何现有成员的等价类相同，则它是冗余的。一些例子：
 *			SELECT ... ORDER BY x, x;
 *			SELECT ... ORDER BY x, x DESC;
 *			SELECT ... WHERE x = y ORDER BY x, y;
 * 在所有这些情况下，第二个排序键无法区分第一个排序键认为相等的值，因此使用它没有意义。
 * 特别注意，我们无需比较运算符族（所有等价类的运算符族对相等的定义相同）或排序方向。
 *
 * 给定的路径键和列表成员都必须是规范的，这样它才能正常工作，但这没关系，因为我们不再构造任何非规范的路径键。 （注意：路径键 *列表* 的规范性概念包括没有冗余条目的额外要求，这正是我们在这里检查的内容。）
 *
 * 由于 equivclass.c 机械在每个查询中仅形成一个 EC 的副本，因此指针比较足以决定规范 EC 是否相同。
 */
static bool fc_pathkey_is_redundant(PathKey *fc_new_pathkey, List *fc_pathkeys)
{
	EquivalenceClass *fc_new_ec = fc_new_pathkey->pk_eclass;
	ListCell   *fc_lc;

	/* 检查包含常量的等价类 --- 无条件冗余 */
	if (EC_MUST_BE_REDUNDANT(fc_new_ec))
		return true;

	/* 如果列表中已使用相同的等价类，则冗余 */
	foreach(fc_lc, fc_pathkeys)
	{
		PathKey    *fc_old_pathkey = (PathKey *) lfirst(fc_lc);

		if (fc_new_ec == fc_old_pathkey->pk_eclass)
			return true;
	}

	return false;
}

/*
 * make_pathkey_from_sortinfo
 *	  给定一个表达式和排序顺序信息，创建一个 PathKey。
 *	  结果始终是一个“规范”的 PathKey，但它可能是冗余的。
 *
 * expr 是表达式，nullable_relids 是在其下可能为空的基本 relids 集。
 *
 * 如果 PathKey 是从 SortGroupClause 生成的，则 sortref 应该是 SortGroupClause 的 SortGroupRef；否则为零。
 *
 * 如果 rel 不是 NULL，它标识我们正在考虑路径的特定关系，并表明可以考虑该关系的子 EC 成员。否则子成员将被忽略。 （请参阅 get_eclass_for_sort_expr 的注释。）
 *
 * create_it 为真表示我们应该创建任何缺失的等价类，以表示排序键。如果为假，则如果排序键在任何等价类中不存在，我们返回 NULL。
 */
static PathKey * fc_make_pathkey_from_sortinfo(PlannerInfo *fc_root,
						   Expr *fc_expr,
						   Relids fc_nullable_relids,
						   Oid fc_opfamily,
						   Oid fc_opcintype,
						   Oid fc_collation,
						   bool fc_reverse_sort,
						   bool fc_nulls_first,
						   Index fc_sortref,
						   Relids fc_rel,
						   bool fc_create_it)
{
	int16		fc_strategy;
	Oid			fc_equality_op;
	List	   *fc_opfamilies;
	EquivalenceClass *fc_eclass;

	fc_strategy = fc_reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;

	/*
	 * 等价类需要包含基于可合并相等运算符的家族成员的运算符族列表，这些运算符可能属于多个运算符族。因此我们必须查找运算符族的相等运算符并获取其成员资格。
	 */
	fc_equality_op = get_opfamily_member(fc_opfamily,
									  fc_opcintype,
									  fc_opcintype,
									  BTEqualStrategyNumber);
	if (!OidIsValid(fc_equality_op))	/* 不应该发生 */
		elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
			 BTEqualStrategyNumber, fc_opcintype, fc_opcintype, fc_opfamily);
	fc_opfamilies = get_mergejoin_opfamilies(fc_equality_op);
	if (!fc_opfamilies)			/* 确实应该找到一些 */
		elog(ERROR, "could not find opfamilies for equality operator %u",
			 fc_equality_op);

	/* 现在查找或（可选）创建一个匹配的等价类 */
	fc_eclass = get_eclass_for_sort_expr(fc_root, fc_expr, fc_nullable_relids,
									  fc_opfamilies, fc_opcintype, fc_collation,
									  fc_sortref, fc_rel, fc_create_it);

	/* 如果没有 EC 且 !create_it，则失败 */
	if (!fc_eclass)
		return NULL;

	/* 最后，我们可以找到或创建一个 PathKey 节点 */
	return make_canonical_pathkey(fc_root, fc_eclass, fc_opfamily,
								  fc_strategy, fc_nulls_first);
}

/*
 * make_pathkey_from_sortop
 *	  类似于 make_pathkey_from_sortinfo，但从排序操作符工作。
 *
 * 这最终应该被废除，但我们需要首先重构 SortGroupClause。
 */
static PathKey * fc_make_pathkey_from_sortop(PlannerInfo *fc_root,
						 Expr *fc_expr,
						 Relids fc_nullable_relids,
						 Oid fc_ordering_op,
						 bool fc_nulls_first,
						 Index fc_sortref,
						 bool fc_create_it)
{
	Oid			fc_opfamily,
				fc_opcintype,
				fc_collation;
	int16		fc_strategy;

	/* 在 pg_amop 中查找操作符 --- 失败不应该发生 */
	if (!get_ordering_op_properties(fc_ordering_op,
									&fc_opfamily, &fc_opcintype, &fc_strategy))
		elog(ERROR, "operator %u is not a valid ordering operator",
			 fc_ordering_op);

	/* 因为 SortGroupClause 不携带排序规则，请查询表达式 */
	fc_collation = exprCollation((Node *) fc_expr);

	return fc_make_pathkey_from_sortinfo(fc_root,
									  fc_expr,
									  fc_nullable_relids,
									  fc_opfamily,
									  fc_opcintype,
									  fc_collation,
									  (fc_strategy == BTGreaterStrategyNumber),
									  fc_nulls_first,
									  fc_sortref,
									  NULL,
									  fc_create_it);
}


/****************************************************************************
 *		PATHKEY 比较
 ****************************************************************************/

/*
 * compare_pathkeys
 *	  比较两个 pathkeys，看看它们是否等价，如果不等价，看看
 *	  是否一个比另一个“更好”。
 *
 *	  我们假设 pathkeys 是规范的，因此它们可以通过简单的指针比较来检查
 *	  是否相等。
 */
PathKeysComparison
compare_pathkeys(List *fc_keys1, List *fc_keys2)
{
	ListCell   *fc_key1,
			   *fc_key2;

	/*
	 * 如果传入两个完全相同的列表，则快速退出。这主要
	 * 捕捉到两者都是 NIL 的情况，但这在一定程度上是
	 * 常见的，因此值得进行测试。
	 */
	if (fc_keys1 == fc_keys2)
		return PATHKEYS_EQUAL;

	forboth(fc_key1, fc_keys1, fc_key2, fc_keys2)
	{
		PathKey    *fc_pathkey1 = (PathKey *) lfirst(fc_key1);
		PathKey    *fc_pathkey2 = (PathKey *) lfirst(fc_key2);

		if (fc_pathkey1 != fc_pathkey2)
			return PATHKEYS_DIFFERENT;	/* 不需要继续查找 */
	}

	/*
	 * 如果我们到达只有一个列表的末尾，另一个列表更长，
	 * 因此不是子集。
	 */
	if (fc_key1 != NULL)
		return PATHKEYS_BETTER1;	/* key1 更长 */
	if (fc_key2 != NULL)
		return PATHKEYS_BETTER2;	/* key2 更长 */
	return PATHKEYS_EQUAL;
}

/*
 * pathkeys_contained_in
 *	  compare_pathkeys 的常见特例：我们只是想知道
 *	  keys2 是否至少和 keys1 一样好地排序。
 */
bool pathkeys_contained_in(List *fc_keys1, List *fc_keys2)
{
	switch (compare_pathkeys(fc_keys1, fc_keys2))
	{
		case PATHKEYS_EQUAL:
		case PATHKEYS_BETTER2:
			return true;
		default:
			break;
	}
	return false;
}

/*
 * pathkeys_count_contained_in
 *	  与 pathkeys_contained_in 相同，但还设置 keys1 和 keys2 的
 *	  最长公共前缀的长度。
 */
bool pathkeys_count_contained_in(List *fc_keys1, List *fc_keys2, int *fc_n_common)
{
	int			fc_n = 0;
	ListCell   *fc_key1,
			   *fc_key2;

	/*
	 * 看看我们是否可以避免循环遍历两个列表。这种优化
	 * 在最坏情况下的测试中为我们节省了几个百分点的规划时间。
	 */
	if (fc_keys1 == fc_keys2)
	{
		*fc_n_common = list_length(fc_keys1);
		return true;
	}
	else if (fc_keys1 == NIL)
	{
		*fc_n_common = 0;
		return true;
	}
	else if (fc_keys2 == NIL)
	{
		*fc_n_common = 0;
		return false;
	}

	/*
	 * 如果两个列表都非空，遍历两个列表以找出有多少
	 * 项目是共享的。
	 */
	forboth(fc_key1, fc_keys1, fc_key2, fc_keys2)
	{
		PathKey    *fc_pathkey1 = (PathKey *) lfirst(fc_key1);
		PathKey    *fc_pathkey2 = (PathKey *) lfirst(fc_key2);

		if (fc_pathkey1 != fc_pathkey2)
		{
			*fc_n_common = fc_n;
			return false;
		}
		fc_n++;
	}

	/* 如果我们结束时为 null 值，那么我们已经处理了整个列表。 */
	*fc_n_common = fc_n;
	return (fc_key1 == NULL);
}

/*
 * get_cheapest_path_for_pathkeys
 *	  找到满足给定 pathkeys 和参数化的最便宜路径（根据指定标准）。
 *	  如果没有这样的路径，则返回 NULL。
 *
 * 'paths' 是生成相同关系的可能路径的列表
 * 'pathkeys' 表示所需的排序（以规范形式！）
 * 'required_outer' 表示参数化路径允许的外部关系
 * 'cost_criterion' 是 STARTUP_COST 或 TOTAL_COST
 * 'require_parallel_safe' 使我们只考虑并行安全的路径
 */
Path * get_cheapest_path_for_pathkeys(List *fc_paths, List *fc_pathkeys,
							   Relids fc_required_outer,
							   CostSelector fc_cost_criterion,
							   bool fc_require_parallel_safe)
{
	Path	   *fc_matched_path = NULL;
	ListCell   *fc_l;

	foreach(fc_l, fc_paths)
	{
		Path	   *fc_path = (Path *) lfirst(fc_l);

		/*
		 * 由于成本比较远比 pathkey 比较便宜，因此首先进行
		 * 成本比较。（XXX 这仍然正确吗？）
		 */
		if (fc_matched_path != NULL &&
			compare_path_costs(fc_matched_path, fc_path, fc_cost_criterion) <= 0)
			continue;

		if (fc_require_parallel_safe && !fc_path->parallel_safe)
			continue;

		if (pathkeys_contained_in(fc_pathkeys, fc_path->pathkeys) &&
			bms_is_subset(PATH_REQ_OUTER(fc_path), fc_required_outer))
			fc_matched_path = fc_path;
	}
	return fc_matched_path;
}

/*
 * get_cheapest_fractional_path_for_pathkeys
 *	  找到满足给定 pathkeys 和参数化的最便宜路径（用于检索指定比例的所有
 *	  元组）。如果没有这样的路径，则返回 NULL。
 *
 * 有关 fraction 参数的解释，请参见 compare_fractional_path_costs()。
 *
 * 'paths' 是生成相同关系的可能路径的列表
 * 'pathkeys' 表示所需的排序（以规范形式！）
 * 'required_outer' 表示参数化路径允许的外部关系
 * 'fraction' 是预计要检索的总元组的比例
 */
Path * get_cheapest_fractional_path_for_pathkeys(List *fc_paths,
										  List *fc_pathkeys,
										  Relids fc_required_outer,
										  double fc_fraction)
{
	Path	   *fc_matched_path = NULL;
	ListCell   *fc_l;

	foreach(fc_l, fc_paths)
	{
		Path	   *fc_path = (Path *) lfirst(fc_l);

		/*
		 * 由于成本比较远比 pathkey 比较便宜，因此首先进行
		 * 成本比较。（XXX 这仍然正确吗？）
		 */
		if (fc_matched_path != NULL &&
			compare_fractional_path_costs(fc_matched_path, fc_path, fc_fraction) <= 0)
			continue;

		if (pathkeys_contained_in(fc_pathkeys, fc_path->pathkeys) &&
			bms_is_subset(PATH_REQ_OUTER(fc_path), fc_required_outer))
			fc_matched_path = fc_path;
	}
	return fc_matched_path;
}


/*
 * get_cheapest_parallel_safe_total_inner
 *	  找到具有最低总成本的未参数化并行安全路径。
 */
Path * get_cheapest_parallel_safe_total_inner(List *fc_paths)
{
	ListCell   *fc_l;

	foreach(fc_l, fc_paths)
	{
		Path	   *fc_innerpath = (Path *) lfirst(fc_l);

		if (fc_innerpath->parallel_safe &&
			bms_is_empty(PATH_REQ_OUTER(fc_innerpath)))
			return fc_innerpath;
	}

	return NULL;
}

/****************************************************************************
 *		新的 PATHKEY 形成
 ****************************************************************************/

/*
 * build_index_pathkeys
 *	  构建一个描述通过给定索引执行的索引扫描引发的排序的 pathkeys 列表。
 *	  （请注意，无序索引不引发任何排序，因此我们返回 NIL。）
 *
 * 如果 'scandir' 为 BackwardScanDirection，则构建表示
 * 索引的向后扫描的 pathkeys。
 *
 * 我们仅迭代覆盖索引的关键列，因为非关键列
 * 不会影响索引排序。结果是规范的，意味着
 * 多余的 pathkeys 被删除；因此，它可能比
 * 索引中的关键列数量更少。
 *
 * 早期停止的另一个原因是，我们可能能够判断
 * 索引列的排序顺序对这个查询没有兴趣。
 * 然而，该测试仅基于 EquivalenceClass 的存在，而不是
 * 基于 pathkey 列表中的位置，因此并不完整。调用者应调用
 * truncate_useless_pathkeys() 以可能删除更多的 pathkeys。
 */
List * build_index_pathkeys(PlannerInfo *fc_root,
					 IndexOptInfo *fc_index,
					 ScanDirection fc_scandir)
{
	List	   *fc_retval = NIL;
	ListCell   *fc_lc;
	int			fc_i;

	if (fc_index->sortopfamily == NULL)
		return NIL;				/* 不可排序的索引 */

	fc_i = 0;
	foreach(fc_lc, fc_index->indextlist)
	{
		TargetEntry *fc_indextle = (TargetEntry *) lfirst(fc_lc);
		Expr	   *fc_indexkey;
		bool		fc_reverse_sort;
		bool		fc_nulls_first;
		PathKey    *fc_cpathkey;

		
/*
		 * INCLUDE 列存储在索引中是无序的，因此不支持有序索引扫描。
		 */
		if (fc_i >= fc_index->nkeycolumns)
			break;

		/* 我们假设不需要复制 tlist 项目 */
		fc_indexkey = fc_indextle->expr;

		if (ScanDirectionIsBackward(fc_scandir))
		{
			fc_reverse_sort = !fc_index->reverse_sort[fc_i];
			fc_nulls_first = !fc_index->nulls_first[fc_i];
		}
		else
		{
			fc_reverse_sort = fc_index->reverse_sort[fc_i];
			fc_nulls_first = fc_index->nulls_first[fc_i];
		}

		/*
		 * 好的，尝试为这个排序键创建一个规范的路径键。 注意我们
		 * 位于任何外连接的下方，因此 nullable_relids 应该为 NULL。
		 */
		fc_cpathkey = fc_make_pathkey_from_sortinfo(fc_root,
											  fc_indexkey,
											  NULL,
											  fc_index->sortopfamily[fc_i],
											  fc_index->opcintype[fc_i],
											  fc_index->indexcollations[fc_i],
											  fc_reverse_sort,
											  fc_nulls_first,
											  0,
											  fc_index->rel->relids,
											  false);

		if (fc_cpathkey)
		{
			/*
			 * 我们在 EquivalenceClass 中找到了排序键，因此它与
			 * 此查询相关。 添加到列表中，除非它是冗余的。
			 */
			if (!fc_pathkey_is_redundant(fc_cpathkey, fc_retval))
				fc_retval = lappend(fc_retval, fc_cpathkey);
		}
		else
		{
			/*
			 * 布尔索引键可能是冗余的，即使它们不
			 * 出现在 EquivalenceClass 中，这是因为我们对布尔相等条件的特殊处理 --- 参见
			 * indexcol_is_bool_constant_for_query() 的注释。 如果适用，我们可以
			 * 继续检查低阶索引列。 否则，排序键对这个查询来说不是
			 * 一个有趣的排序顺序，因此我们应该停止考虑索引列；任何低阶排序
			 * 键也不会有用。
			 */
			if (!indexcol_is_bool_constant_for_query(fc_root, fc_index, fc_i))
				break;
		}

		fc_i++;
	}

	return fc_retval;
}

/*
 * partkey_is_bool_constant_for_query
 *
 * 如果分区键列因查询的 WHERE 条件被约束为具有常量值，那么它在排序顺序考虑中就无关紧要。通常这意味着我们有一个限制子句 WHERE partkeycol = constant，这被转换为一个包含常量的 EquivalenceClass，这在 build_partition_pathkeys() 中被识别为多余。但如果分区键列是布尔变量（或表达式），那么我们不会看到这样的 WHERE 子句，因为表达式预处理会将其简化为 "WHERE partkeycol" 或 "WHERE NOT partkeycol"。因此，我们不会有匹配的 EquivalenceClass（除非查询也包含 "ORDER BY partkeycol"）。为了使这种情况与非布尔值的情况一样工作，提供了此函数以检测指定的分区键列是否匹配布尔限制子句。
 */
static bool fc_partkey_is_bool_constant_for_query(RelOptInfo *fc_partrel, int fc_partkeycol)
{
	PartitionScheme fc_partscheme = fc_partrel->part_scheme;
	ListCell   *fc_lc;

	/* 如果 partkey 不是布尔值，我们不可能得到匹配 */
	if (!IsBooleanOpfamily(fc_partscheme->partopfamily[fc_partkeycol]))
		return false;

	/* 检查分区关系的每个限制子句 */
	foreach(fc_lc, fc_partrel->baserestrictinfo)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_lc);

		/* 忽略伪常量限制，因为它们不会匹配 */
		if (fc_rinfo->pseudoconstant)
			continue;

		/* 查看我们是否能将子句的表达式匹配到 partkey 列 */
		if (fc_matches_boolean_partition_clause(fc_rinfo, fc_partrel, fc_partkeycol))
			return true;
	}

	return false;
}

/*
 * matches_boolean_partition_clause
 *      确定 rinfo 描述的布尔子句是否与 partrel 的 partkeycol-th 分区键列匹配。
 *
 * “匹配”可以是精确匹配（相当于 partkey = true），
 * 或在精确匹配上加个 NOT（相当于 partkey = false）。
 */
static bool fc_matches_boolean_partition_clause(RestrictInfo *fc_rinfo,
								 RelOptInfo *fc_partrel, int fc_partkeycol)
{
	Node	   *fc_clause = (Node *) fc_rinfo->clause;
	Node	   *fc_partexpr = (Node *) linitial(fc_partrel->partexprs[fc_partkeycol]);

	/* 直接匹配？ */
	if (equal(fc_partexpr, fc_clause))
		return true;
	/* NOT 子句？ */
	else if (is_notclause(fc_clause))
	{
		Node	   *fc_arg = (Node *) get_notclausearg((Expr *) fc_clause);

		if (equal(fc_partexpr, fc_arg))
			return true;
	}

	return false;
}

/*
 * build_partition_pathkeys
 *      构建一个描述由 partrel 的分区所诱导的排序的 pathkeys 列表，
 *      无论是向前还是向后扫描，根据 scandir。
 *
 * 调用者必须检查分区是否正确排序，
 * 通过 partitions_are_ordered() 进行检测。
 *
 * 如果 pathkeys 仅针对分区键的前缀构建，则将 *partialkeys 设置为 true，
 * 如果 pathkeys 包含分区键的所有列，则设置为 false。
 */
List * build_partition_pathkeys(PlannerInfo *fc_root, RelOptInfo *fc_partrel,
						 ScanDirection fc_scandir, bool *fc_partialkeys)
{
	List	   *fc_retval = NIL;
	PartitionScheme fc_partscheme = fc_partrel->part_scheme;
	int			fc_i;

	Assert(fc_partscheme != NULL);
	Assert(partitions_are_ordered(fc_partrel->boundinfo, fc_partrel->live_parts));
	/* 暂时，我们只能处理基关系 */
	Assert(IS_SIMPLE_REL(fc_partrel));

	for (fc_i = 0; fc_i < fc_partscheme->partnatts; fc_i++)
	{
		PathKey    *fc_cpathkey;
		Expr	   *fc_keyCol = (Expr *) linitial(fc_partrel->partexprs[fc_i]);

		/*
         * 尝试为这个 partkey 制作一个规范的 pathkey。
         *
         * 我们正在考虑一个基关系扫描，因此 nullable_relids 应为
         * NULL。同时，我们假设 PartitionDesc 将任何 NULL 分区
         * 放在最后，因此我们将扫描视为一个 NULLS LAST 索引：我们
         * 只有在向后扫描时有 nulls_first。
         */
		fc_cpathkey = fc_make_pathkey_from_sortinfo(fc_root,
											  fc_keyCol,
											  NULL,
											  fc_partscheme->partopfamily[fc_i],
											  fc_partscheme->partopcintype[fc_i],
											  fc_partscheme->partcollation[fc_i],
											  ScanDirectionIsBackward(fc_scandir),
											  ScanDirectionIsBackward(fc_scandir),
											  0,
											  fc_partrel->relids,
											  false);


		if (fc_cpathkey)
		{
			/*
			 * 我们在 EquivalenceClass 中找到了排序键，因此它与
			 * 此查询相关。 添加到列表中，除非它是冗余的。
			 */
			if (!fc_pathkey_is_redundant(fc_cpathkey, fc_retval))
				fc_retval = lappend(fc_retval, fc_cpathkey);
		}
		else
		{
			/*
             * 即使布尔分区键不出现在 EquivalenceClass 中，
             * 由于我们对布尔相等条件的特殊处理，它们可能是多余的 --- 
             * 参见 partkey_is_bool_constant_for_query() 的注释。
             * 如果适用，我们可以继续检查低阶分区键。
             * 否则，排序键对这个查询不是有趣的排序顺序，
             * 所以我们应该停止考虑分区列；任何低阶排序
             * 键也不会有用。
             */
			if (!fc_partkey_is_bool_constant_for_query(fc_partrel, fc_i))
			{
				*fc_partialkeys = true;
				return fc_retval;
			}
		}
	}

	*fc_partialkeys = false;
	return fc_retval;
}

/*
 * build_expression_pathkey
 *      构建一个描述单个表达式排序的 pathkeys 列表，
 *      使用给定的排序操作符。
 *
 * expr、nullable_relids 和 rel 的形式与 make_pathkey_from_sortinfo 一致。
 * 我们假设默认的操作符排序顺序来引导其他参数。
 *
 * 与 make_pathkey_from_sortinfo 类似，如果 create_it 为 false 而
 * 表达式尚未在某个 EquivalenceClass 中，则结果为 NIL。
 */
List * build_expression_pathkey(PlannerInfo *fc_root,
						 Expr *fc_expr,
						 Relids fc_nullable_relids,
						 Oid fc_opno,
						 Relids fc_rel,
						 bool fc_create_it)
{
	List	   *fc_pathkeys;
	Oid			fc_opfamily,
				fc_opcintype;
	int16		fc_strategy;
	PathKey    *fc_cpathkey;

	/* 在 pg_amop 中查找操作符 --- 失败不应该发生 */
	if (!get_ordering_op_properties(fc_opno,
									&fc_opfamily, &fc_opcintype, &fc_strategy))
		elog(ERROR, "operator %u is not a valid ordering operator",
			 fc_opno);

	fc_cpathkey = fc_make_pathkey_from_sortinfo(fc_root,
										  fc_expr,
										  fc_nullable_relids,
										  fc_opfamily,
										  fc_opcintype,
										  exprCollation((Node *) fc_expr),
										  (fc_strategy == BTGreaterStrategyNumber),
										  (fc_strategy == BTGreaterStrategyNumber),
										  0,
										  fc_rel,
										  fc_create_it);

	if (fc_cpathkey)
		fc_pathkeys = list_make1(fc_cpathkey);
	else
		fc_pathkeys = NIL;

	return fc_pathkeys;
}

/*
 * convert_subquery_pathkeys
 *      构建一个描述子查询结果排序的 pathkeys 列表，
 *      用外部查询的术语。这本质上是一项转换任务。
 *
 * 'rel'：外部查询的子查询关系的 RelOptInfo。
 * 'subquery_pathkeys'：子查询的输出 pathkeys，以其术语表示。
 * 'subquery_tlist'：子查询的输出目标列表，以其术语表示。
 *
 * 我们故意不在这里执行 truncate_useless_pathkeys()，
 * 因为有些情况下看到子查询的原始排序是有帮助的。
 * 例如，如果它返回 ORDER BY x DESC，这可能促使我们
 * 使用 DESC 排序而非 ASC 排序构造一个合并连接；
 * 但是 right_merge_direction 启发式会让我们丢弃这一知识。
 */
List * convert_subquery_pathkeys(PlannerInfo *fc_root, RelOptInfo *fc_rel,
						  List *fc_subquery_pathkeys,
						  List *fc_subquery_tlist)
{
	List	   *fc_retval = NIL;
	int			fc_retvallen = 0;
	int			fc_outer_query_keys = list_length(fc_root->query_pathkeys);
	ListCell   *fc_i;

	foreach(fc_i, fc_subquery_pathkeys)
	{
		PathKey    *fc_sub_pathkey = (PathKey *) lfirst(fc_i);
		EquivalenceClass *fc_sub_eclass = fc_sub_pathkey->pk_eclass;
		PathKey    *fc_best_pathkey = NULL;

		if (fc_sub_eclass->ec_has_volatile)
		{
			/*
             * 如果 sub_pathkey 的 EquivalenceClass 是易变的，
             * 那么它必须来自一个 ORDER BY 子句，
             * 我们必须将其匹配到同一个目标列表条目。
             */
			TargetEntry *fc_tle;
			Var		   *fc_outer_var;

			if (fc_sub_eclass->ec_sortref == 0)	/* 不能发生 */
				elog(ERROR, "volatile EquivalenceClass has no sortref");
			fc_tle = get_sortgroupref_tle(fc_sub_eclass->ec_sortref, fc_subquery_tlist);
			Assert(fc_tle);
			/* TLE 实际上对外部查询可用吗？ */
			fc_outer_var = fc_find_var_for_subquery_tle(fc_rel, fc_tle);
			if (fc_outer_var)
			{
				/* 我们可以表示这个 sub_pathkey */
				EquivalenceMember *fc_sub_member;
				EquivalenceClass *fc_outer_ec;

				Assert(list_length(fc_sub_eclass->ec_members) == 1);
				fc_sub_member = (EquivalenceMember *) linitial(fc_sub_eclass->ec_members);

				
/*
				 * 注意：将 sortref 设置为 0 用于对 volatile sub_eclass 的引用可能看起来很奇怪。
				 * 然而，外部查询中的表达式*不是*易失性的：它只是一个 Var，引用了子查询发出的任何内容。
				 * （换句话说，外部查询不会重新执行易失性的表达式本身。）所以这是可以的。同样，传递 nullable_relids = NULL 也是正确的，
				 * 因为我们在外部查询中出现的任何外联接之下。
				 */
				fc_outer_ec =
					get_eclass_for_sort_expr(fc_root,
											 (Expr *) fc_outer_var,
											 NULL,
											 fc_sub_eclass->ec_opfamilies,
											 fc_sub_member->em_datatype,
											 fc_sub_eclass->ec_collation,
											 0,
											 fc_rel->relids,
											 false);

				/*
				 * 如果我们找不到匹配的 EC，sub-pathkey 对外部查询就没意义
				 */
				if (fc_outer_ec)
					fc_best_pathkey =
						make_canonical_pathkey(fc_root,
											   fc_outer_ec,
											   fc_sub_pathkey->pk_opfamily,
											   fc_sub_pathkey->pk_strategy,
											   fc_sub_pathkey->pk_nulls_first);
			}
		}
		else
		{
			/*
			 * 否则，sub_pathkey 的 EquivalenceClass 可能包含多个元素（代表多个项目
			 * 实际上是相等的知识）。每个元素可能与外部查询可见的输出列没有匹配、
			 * 有一个匹配或有多个匹配。这意味着我们可能在外部查询的上下文中有多个可能的
			 * sub_pathkey 表示。理想情况下，我们会生成所有这些表示并将它们全部放入外部查询的 EC 中，
			 * 从而将相等知识传播到外部查询。目前我们无法做到这一点，因为在调用时外部查询的
			 * EquivalenceClasses 已经被冻结。相反，我们更喜欢得分最高的那一个
			 * （EC 同伴的数量，加上一，如果它与外部查询的 query_pathkeys 匹配）。这最可能在外部查询中有用。
			 */
			int			fc_best_score = -1;
			ListCell   *fc_j;

			foreach(fc_j, fc_sub_eclass->ec_members)
			{
				EquivalenceMember *fc_sub_member = (EquivalenceMember *) lfirst(fc_j);
				Expr	   *fc_sub_expr = fc_sub_member->em_expr;
				Oid			fc_sub_expr_type = fc_sub_member->em_datatype;
				Oid			fc_sub_expr_coll = fc_sub_eclass->ec_collation;
				ListCell   *fc_k;

				if (fc_sub_member->em_is_child)
					continue;	/* 在这里忽略子项 */

				foreach(fc_k, fc_subquery_tlist)
				{
					TargetEntry *fc_tle = (TargetEntry *) lfirst(fc_k);
					Var		   *fc_outer_var;
					Expr	   *fc_tle_expr;
					EquivalenceClass *fc_outer_ec;
					PathKey    *fc_outer_pk;
					int			fc_score;

					/* TLE 实际上对外部查询可用吗？ */
					fc_outer_var = fc_find_var_for_subquery_tle(fc_rel, fc_tle);
					if (!fc_outer_var)
						continue;

					/*
					 * 如果目标列表条目经过排序键规范化后匹配，则认为它匹配。
					 * 这是需要的，因为 sub_expr 已经过同样的处理。
					 */
					fc_tle_expr = canonicalize_ec_expression(fc_tle->expr,
														  fc_sub_expr_type,
														  fc_sub_expr_coll);
					if (!equal(fc_tle_expr, fc_sub_expr))
						continue;

					/* 查看我们是否有与 TLE 匹配的 EC */
					fc_outer_ec = get_eclass_for_sort_expr(fc_root,
														(Expr *) fc_outer_var,
														NULL,
														fc_sub_eclass->ec_opfamilies,
														fc_sub_expr_type,
														fc_sub_expr_coll,
														0,
														fc_rel->relids,
														false);

					/*
					 * 如果我们找不到匹配的 EC，这个 sub-pathkey 对外部查询就没兴趣
					 */
					if (!fc_outer_ec)
						continue;

					fc_outer_pk = make_canonical_pathkey(fc_root,
													  fc_outer_ec,
													  fc_sub_pathkey->pk_opfamily,
													  fc_sub_pathkey->pk_strategy,
													  fc_sub_pathkey->pk_nulls_first);
					/* score = 相等同伴的数量 */
					fc_score = list_length(fc_outer_ec->ec_members) - 1;
					/* +1 如果它与正确的 query_pathkeys 项目匹配 */
					if (fc_retvallen < fc_outer_query_keys &&
						list_nth(fc_root->query_pathkeys, fc_retvallen) == fc_outer_pk)
						fc_score++;
					if (fc_score > fc_best_score)
					{
						fc_best_pathkey = fc_outer_pk;
						fc_best_score = fc_score;
					}
				}
			}
		}

		/*
		 * 如果我们找不到此 sub_pathkey 的表示，我们就完成了（我们也无法使用它右侧的表示）。
		 */
		if (!fc_best_pathkey)
			break;

		/*
		 * 消除冗余的排序信息；如果外部查询的
		 * 等价子查询键...可能会发生这种情况。
		 */
		if (!fc_pathkey_is_redundant(fc_best_pathkey, fc_retval))
		{
			fc_retval = lappend(fc_retval, fc_best_pathkey);
			fc_retvallen++;
		}
	}

	return fc_retval;
}

/*
 * find_var_for_subquery_tle
 *
 * 如果给定的子查询 tlist 条目预期由子查询的
 * 扫描节点发出，返回一个 Var，否则返回 NULL。
 *
 * 我们需要这个来确保我们不会返回描述在子查询扫描级别以上不可用的值的 pathkeys。
 */
static Var * fc_find_var_for_subquery_tle(RelOptInfo *fc_rel, TargetEntry *fc_tle)
{
	ListCell   *fc_lc;

	/* 如果 TLE 是 resjunk，它当然在外部查询中不可见 */
	if (fc_tle->resjunk)
		return NULL;

	/* 搜索 rel 的目标列表以查看它将返回什么 */
	foreach(fc_lc, fc_rel->reltarget->exprs)
	{
		Var		   *fc_var = (Var *) lfirst(fc_lc);

		/* 忽略占位符 */
		if (!IsA(fc_var, Var))
			continue;
		Assert(fc_var->varno == fc_rel->relid);

		/* 如果我们找到一个引用这个 TLE 的 Var，我们就成功了 */
		if (fc_var->varattno == fc_tle->resno)
			return copyObject(fc_var); /* 为了安全起见，复制一份 */
	}
	return NULL;
}

/*
 * build_join_pathkeys
 *	  为通过 mergejoin 或 nestloop join 构造的连接关系构建路径键。 这通常与外部路径的键相同。
 *
 *	  例外：在 FULL 或 RIGHT 连接中，我们不能将结果视为具有外部路径的路径键，因为可能会在随机位置插入空的左侧行。 这必须视为无序。
 *
 *	  我们截断任何对更高连接不感兴趣的路径键。
 *
 * 'joinrel' 是要为其形成路径的连接关系
 * 'jointype' 是连接类型（内部、左、完全等）
 * 'outer_pathkeys' 是当前外部路径的路径键列表
 *
 * 返回新的路径键列表。
 */
List * build_join_pathkeys(PlannerInfo *fc_root,
					RelOptInfo *fc_joinrel,
					JoinType fc_jointype,
					List *fc_outer_pathkeys)
{
	if (fc_jointype == JOIN_FULL || fc_jointype == JOIN_RIGHT)
		return NIL;

	/*
	 * 这曾经是一段相当复杂的代码，但由于所有路径键子列表的生命周期都经过规范化，我们在这里不需要做任何事情！
	 *
	 * 然而，我们确实需要截断路径键列表，因为它可能包含对形成这个 joinrel 有用但对更高层次不感兴趣的路径键。
	 */
	return truncate_useless_pathkeys(fc_root, fc_joinrel, fc_outer_pathkeys);
}

/****************************************************************************
 *		PATHKEYS 和 SORT CLAUSES
 ****************************************************************************/

/*
 * make_pathkeys_for_sortclauses
 *		生成一个表示由 SortGroupClauses 列表指定的排序顺序的路径键列表
 *
 * 生成的 PathKeys 始终是规范形式。 (实际上，任何地方都没有代码会创建非规范 PathKeys。)
 *
 * 我们假设 root->nullable_baserels 是可能在 SortGroupClause 表达式下变为 NULL 的基本 relid 集。 如果这些表达式来自查询的顶层（ORDER BY、DISTINCT 等），并且仅在 deconstruct_jointree 之后调用此函数，这就没问题。 在未来，我们可能需要让调用者传递适当的可为空的 relids 集，但目前似乎没有必要。
 *
 * 'sortclauses' 是 SortGroupClause 节点的列表
 * 'tlist' 是目标列表以查找引用的 tlist 条目
 */
List * make_pathkeys_for_sortclauses(PlannerInfo *fc_root,
							  List *fc_sortclauses,
							  List *fc_tlist)
{
	List	   *fc_pathkeys = NIL;
	ListCell   *fc_l;

	foreach(fc_l, fc_sortclauses)
	{
		SortGroupClause *fc_sortcl = (SortGroupClause *) lfirst(fc_l);
		Expr	   *fc_sortkey;
		PathKey    *fc_pathkey;

		fc_sortkey = (Expr *) get_sortgroupclause_expr(fc_sortcl, fc_tlist);
		Assert(OidIsValid(fc_sortcl->sortop));
		fc_pathkey = fc_make_pathkey_from_sortop(fc_root,
										   fc_sortkey,
										   fc_root->nullable_baserels,
										   fc_sortcl->sortop,
										   fc_sortcl->nulls_first,
										   fc_sortcl->tleSortGroupRef,
										   true);

		/* 规范形式消除了冗余的排序键 */
		if (!fc_pathkey_is_redundant(fc_pathkey, fc_pathkeys))
			fc_pathkeys = lappend(fc_pathkeys, fc_pathkey);
	}
	return fc_pathkeys;
}

/****************************************************************************
 *		PATHKEYS 和 MERGECLAUSES
 ****************************************************************************/

/*
 * initialize_mergeclause_eclasses
 *		在 mergeclause restrictinfo 中设置等价类链接。
 *
 * RestrictInfo 包含我们可以为 mergeclause 的左侧和右侧输入缓存指向等价类的指针的字段。 （如果 mergeclause 是一个真正的等价子句，则这些将是同一个等价类，否则不是。）如果 mergeclause 用于生成等价类，或者源自等价类，则很容易设置 left_ec 和 right_ec 成员——否则，应该调用此函数进行设置。 如果有必要，我们将生成新的等价子句以表示 mergeclause 的左侧和右侧。
 *
 * 请注意，这是在 EC 合并尚未完成之前调用的，因此链接不一定指向规范的 EC。 在它们实际用于任何内容之前，必须调用 update_mergeclause_eclasses 以确保它们已更新为指向规范的 EC。
 */
void initialize_mergeclause_eclasses(PlannerInfo *fc_root, RestrictInfo *fc_restrictinfo)
{
	Expr	   *fc_clause = fc_restrictinfo->clause;
	Oid			fc_lefttype,
				fc_righttype;

	/* 应该是一个 mergeclause ... */
	Assert(fc_restrictinfo->mergeopfamilies != NIL);
	/* ... 但链接尚未设置 */
	Assert(fc_restrictinfo->left_ec == NULL);
	Assert(fc_restrictinfo->right_ec == NULL);

	/* 需要操作符的声明输入类型 */
	op_input_types(((OpExpr *) fc_clause)->opno, &fc_lefttype, &fc_righttype);

	/* 为每一侧查找或创建匹配的等价类 */
	fc_restrictinfo->left_ec =
		get_eclass_for_sort_expr(fc_root,
								 (Expr *) get_leftop(fc_clause),
								 fc_restrictinfo->nullable_relids,
								 fc_restrictinfo->mergeopfamilies,
								 fc_lefttype,
								 ((OpExpr *) fc_clause)->inputcollid,
								 0,
								 NULL,
								 true);
	fc_restrictinfo->right_ec =
		get_eclass_for_sort_expr(fc_root,
								 (Expr *) get_rightop(fc_clause),
								 fc_restrictinfo->nullable_relids,
								 fc_restrictinfo->mergeopfamilies,
								 fc_righttype,
								 ((OpExpr *) fc_clause)->inputcollid,
								 0,
								 NULL,
								 true);
}

/*
 * update_mergeclause_eclasses
 *		使 mergeclause restrictinfo 中缓存的等价类链接有效。
 *
 * 这些指针应该由 process_equivalence 或 initialize_mergeclause_eclasses 设置，但它们可能已设置为稍后合并的非规范 EC。 如果是这样，请向上追溯到规范的合并父类。
 */
void update_mergeclause_eclasses(PlannerInfo *fc_root, RestrictInfo *fc_restrictinfo)
{
	/* 应该是一个 merge 子句 ... */
	Assert(fc_restrictinfo->mergeopfamilies != NIL);
	/* ... 指针已经设置 */
	Assert(fc_restrictinfo->left_ec != NULL);
	Assert(fc_restrictinfo->right_ec != NULL);

	/* 根据需要向上追溯 */
	while (fc_restrictinfo->left_ec->ec_merged)
		fc_restrictinfo->left_ec = fc_restrictinfo->left_ec->ec_merged;
	while (fc_restrictinfo->right_ec->ec_merged)
		fc_restrictinfo->right_ec = fc_restrictinfo->right_ec->ec_merged;
}


/*
 * find_mergeclauses_for_outer_pathkeys
 *	  此例程尝试查找可以用于指定连接外关系的排序的合并子句列表。
 *	  如果成功，它将返回一个合并子句的列表。
 *
 * 'pathkeys' 是一个路径键列表，显示了外部关系路径的排序。
 * 'restrictinfos' 是一个合并可连接的限制子句列表，针对正在形成的连接关系，没有特定的顺序。
 *
 * restrictinfos 必须通过 outer_is_left 标记，以显示每个子句的哪一侧与当前外部路径相关。 （请参阅 select_mergejoin_clauses()）
 *
 * 如果不能进行合并，则结果为 NIL，否则是可用合并子句的最大列表（表示为其 restrictinfo 节点的列表）。
 * 此列表的顺序与 pathkeys 匹配，这是执行所要求的。
 */
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *fc_root,
									 List *fc_pathkeys,
									 List *fc_restrictinfos)
{
	List	   *fc_mergeclauses = NIL;
	ListCell   *fc_i;

	/* 确保我们在子句中缓存了 eclasses */
	foreach(fc_i, fc_restrictinfos)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_i);

		update_mergeclause_eclasses(fc_root, fc_rinfo);
	}

	foreach(fc_i, fc_pathkeys)
	{
		PathKey    *fc_pathkey = (PathKey *) lfirst(fc_i);
		EquivalenceClass *fc_pathkey_ec = fc_pathkey->pk_eclass;
		List	   *fc_matched_restrictinfos = NIL;
		ListCell   *fc_j;

		/*----------
		 * 如果合并连接子句具有相同的等价类 (EC)，则合并连接子句与路径键匹配。
		 * 如果有多个匹配的子句，则全部取出。在简单的
		 * 内连接场景中，我们预计只会有一个匹配，因为
		 * 等价类处理将删除任何冗余的
		 * 合并子句。然而，在外连接场景中可能会有
		 * 多个匹配。例如：
		 *
		 *	select * from a full join b
		 *		on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
		 *
		 * 给定路径键 ({a.v1}, {a.v2})，返回所有三个
		 * 子句（按 a.v1=b.v1、a.v1=b.v2、a.v2=b.v2 的顺序）是可以的，实际上
		 * 我们 *必须* 这样做，否则将无法形成有效的计划。
		 *
		 * 我们期望给定的路径键列表是规范的，这意味着
		 * 没有两个成员具有相同的 EC，因此该
		 * 代码无法将相同的合并子句两次输入结果列表。
		 *
		 * 可能多个匹配子句在另一侧具有不同的
		 * EC，在这种情况下，我们将它们放入结果中的顺序会影响内
		 * 输入关系所需的路径键。然而，此例程没有信息表明
		 * 哪种顺序最好，因此我们不担心这个问题。
		 *
		 * 还可能选择的合并连接子句产生内侧路径键的非规范排序，即，我们
		 * 可能会选择以 b.v1、b.v2、b.v1 的顺序引用的子句。这本身并不有害，但它暗示
		 * 这些子句部分冗余。由于替代方案是
		 * 删除合并连接子句，从而可能完全无法生成
		 * 计划，我们接受这个限制。make_inner_pathkeys_for_merge()
		 * 在构建内部路径键列表时必须删除重复项，
		 * 我们在 create_mergejoin_plan() 中还必须特别处理这种情况。
		 *----------
		 */
		foreach(fc_j, fc_restrictinfos)
		{
			RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_j);
			EquivalenceClass *fc_clause_ec;

			fc_clause_ec = fc_rinfo->outer_is_left ?
				fc_rinfo->left_ec : fc_rinfo->right_ec;
			if (fc_clause_ec == fc_pathkey_ec)
				fc_matched_restrictinfos = lappend(fc_matched_restrictinfos, fc_rinfo);
		}

		/*
		 * 如果未找到合并子句，我们就完成了——路径键中的任何额外
		 * 排序键位置都是无用的。（但是如果至少找到了一个合并子句，我们仍然可以合并连接。）
		 */
		if (fc_matched_restrictinfos == NIL)
			break;

		/*
		 * 如果我们为此排序键位置找到了可用的合并子句，
		 * 则将它们添加到结果列表中。
		 */
		fc_mergeclauses = list_concat(fc_mergeclauses, fc_matched_restrictinfos);
	}

	return fc_mergeclauses;
}

/*
 * select_outer_pathkeys_for_merge
 *	  构建一个路径键列表，表示可以与给定合并子句一起使用的可能排序顺序。
 *
 * 'mergeclauses' 是一个合并连接子句的 RestrictInfos 列表，
 *			将在合并连接中使用。
 * 'joinrel' 是我们试图构建的连接关系。
 *
 * restrictinfos 必须通过 outer_is_left 标记，以显示每个子句的哪一侧与当前外部路径相关。 （请参阅 select_mergejoin_clauses()）
 *
 * 返回一个可以应用于外部关系的路径键列表。
 *
 * 由于我们在这里假设需要排序，因此与外部关系的可用排序匹配并没有特别的用处。 
 * （joinpath.c 有一个完全独立的代码路径用于考虑无排序的合并连接。）相反， 
 * 尝试匹配请求的查询路径键是很有趣的，以便避免第二次输出排序； 
 * 如果失败，我们试图更早列出“更受欢迎”的键（那些与最多未匹配的等价类同行的键）， 
 * 希望使最终排序对尽可能多的更高层合并连接有用。
 */
List * select_outer_pathkeys_for_merge(PlannerInfo *fc_root,
								List *fc_mergeclauses,
								RelOptInfo *fc_joinrel)
{
	List	   *fc_pathkeys = NIL;
	int			fc_nClauses = list_length(fc_mergeclauses);
	EquivalenceClass **fc_ecs;
	int		   *fc_scores;
	int			fc_necs;
	ListCell   *fc_lc;
	int			fc_j;

	/* 可能没有合并子句 */
	if (fc_nClauses == 0)
		return NIL;

	/*
	 * 制作合并子句使用的 EC 的数组（去除任何
	 * 重复）及其“受欢迎程度”分数。
	 */
	fc_ecs = (EquivalenceClass **) palloc(fc_nClauses * sizeof(EquivalenceClass *));
	fc_scores = (int *) palloc(fc_nClauses * sizeof(int));
	fc_necs = 0;

	foreach(fc_lc, fc_mergeclauses)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_lc);
		EquivalenceClass *fc_oeclass;
		int			fc_score;
		ListCell   *fc_lc2;

		/* 获取外部 eclass */
		update_mergeclause_eclasses(fc_root, fc_rinfo);

		if (fc_rinfo->outer_is_left)
			fc_oeclass = fc_rinfo->left_ec;
		else
			fc_oeclass = fc_rinfo->right_ec;

		/* 排除重复项 */
		for (fc_j = 0; fc_j < fc_necs; fc_j++)
		{
			if (fc_ecs[fc_j] == fc_oeclass)
				break;
		}
		if (fc_j < fc_necs)
			continue;

		
		fc_score = 0;
		foreach(fc_lc2, fc_oeclass->ec_members)
		{
			EquivalenceMember *fc_em = (EquivalenceMember *) lfirst(fc_lc2);

			/* 潜在的未来连接伙伴？ */
			if (!fc_em->em_is_const && !fc_em->em_is_child &&
				!bms_overlap(fc_em->em_relids, fc_joinrel->relids))
				fc_score++;
		}

		fc_ecs[fc_necs] = fc_oeclass;
		fc_scores[fc_necs] = fc_score;
		fc_necs++;
	}

	/*
	 * 查找我们是否拥有查询路径键中提到的所有 EC；如果有的话，我们
	 * 可以生成对最终输出也有用的排序顺序。不过，部分匹配是没有意义的，
	 * 因此我们必须拥有全部。
	 */
	if (fc_root->query_pathkeys)
	{
		foreach(fc_lc, fc_root->query_pathkeys)
		{
			PathKey    *fc_query_pathkey = (PathKey *) lfirst(fc_lc);
			EquivalenceClass *fc_query_ec = fc_query_pathkey->pk_eclass;

			for (fc_j = 0; fc_j < fc_necs; fc_j++)
			{
				if (fc_ecs[fc_j] == fc_query_ec)
					break;		/* 找到匹配 */
			}
			if (fc_j >= fc_necs)
				break;			/* 没有找到匹配 */
		}
		/* 如果我们到达列表的末尾，我们就拥有它们全部 */
		if (fc_lc == NULL)
		{
			/* 复制查询路径键作为我们输出的起始点 */
			fc_pathkeys = list_copy(fc_root->query_pathkeys);
			/* 将它们的 EC 标记为已发出 */
			foreach(fc_lc, fc_root->query_pathkeys)
			{
				PathKey    *fc_query_pathkey = (PathKey *) lfirst(fc_lc);
				EquivalenceClass *fc_query_ec = fc_query_pathkey->pk_eclass;

				for (fc_j = 0; fc_j < fc_necs; fc_j++)
				{
					if (fc_ecs[fc_j] == fc_query_ec)
					{
						fc_scores[fc_j] = -1;
						break;
					}
				}
			}
		}
	}

	/*
	 * 按受欢迎程度顺序将剩余 EC 添加到列表中，使用默认排序
	 * 顺序。（我们可以在这里使用 qsort()，但列表长度通常
	 * 很小，因此不值得。）
	 */
	for (;;)
	{
		int			fc_best_j;
		int			fc_best_score;
		EquivalenceClass *fc_ec;
		PathKey    *fc_pathkey;

		fc_best_j = 0;
		fc_best_score = fc_scores[0];
		for (fc_j = 1; fc_j < fc_necs; fc_j++)
		{
			if (fc_scores[fc_j] > fc_best_score)
			{
				fc_best_j = fc_j;
				fc_best_score = fc_scores[fc_j];
			}
		}
		if (fc_best_score < 0)
			break;				/* 全部完成 */
		fc_ec = fc_ecs[fc_best_j];
		fc_scores[fc_best_j] = -1;
		fc_pathkey = make_canonical_pathkey(fc_root,
										 fc_ec,
										 linitial_oid(fc_ec->ec_opfamilies),
										 BTLessStrategyNumber,
										 false);
		/* 不能是冗余的，因为没有重复的 EC */
		Assert(!fc_pathkey_is_redundant(fc_pathkey, fc_pathkeys));
		fc_pathkeys = lappend(fc_pathkeys, fc_pathkey);
	}

	pfree(fc_ecs);
	pfree(fc_scores);

	return fc_pathkeys;
}

/*
 * make_inner_pathkeys_for_merge
 *	  构建一个路径键列表，表示必须应用于内部路径的显式排序顺序，
 *	  使其可与给定的 mergeclauses 一起使用。
 *
 * 'mergeclauses' 是一个用于 mergejoin 子句的 RestrictInfos 列表，
 *		 按顺序将在合并连接中使用。
 * 'outer_pathkeys' 是连接外侧已知的标准路径键。
 *
 * restrictinfos 必须标记（通过 outer_is_left）以表明每个子句的哪一侧
 * 与当前的外部路径相关联。（见 select_mergejoin_clauses()）
 *
 * 返回可以应用于内部关系的路径键列表。
 *
 * 请注意，这个例程的工作不是决定特定输入路径是否确实需要排序。
 * 假设需要排序；只需生成键。
 */
List * make_inner_pathkeys_for_merge(PlannerInfo *fc_root,
							  List *fc_mergeclauses,
							  List *fc_outer_pathkeys)
{
	List	   *fc_pathkeys = NIL;
	EquivalenceClass *fc_lastoeclass;
	PathKey    *fc_opathkey;
	ListCell   *fc_lc;
	ListCell   *fc_lop;

	fc_lastoeclass = NULL;
	fc_opathkey = NULL;
	fc_lop = list_head(fc_outer_pathkeys);

	foreach(fc_lc, fc_mergeclauses)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_lc);
		EquivalenceClass *fc_oeclass;
		EquivalenceClass *fc_ieclass;
		PathKey    *fc_pathkey;

		update_mergeclause_eclasses(fc_root, fc_rinfo);

		if (fc_rinfo->outer_is_left)
		{
			fc_oeclass = fc_rinfo->left_ec;
			fc_ieclass = fc_rinfo->right_ec;
		}
		else
		{
			fc_oeclass = fc_rinfo->right_ec;
			fc_ieclass = fc_rinfo->left_ec;
		}

		/* 外部 eclass 应该与当前或下一个路径键匹配 */
		/* 我们仔细检查这一点以进行调试 */
		if (fc_oeclass != fc_lastoeclass)
		{
			if (!fc_lop)
				elog(ERROR, "too few pathkeys for mergeclauses");
			fc_opathkey = (PathKey *) lfirst(fc_lop);
			fc_lop = lnext(fc_outer_pathkeys, fc_lop);
			fc_lastoeclass = fc_opathkey->pk_eclass;
			if (fc_oeclass != fc_lastoeclass)
				elog(ERROR, "outer pathkeys do not match mergeclause");
		}

		/*
		 * 通常，我们在两侧都有相同的 EC，在这种情况下，外部
		 * 路径键对于内部侧也是规范的，我们可以跳过
		 * 无用的搜索。
		 */
		if (fc_ieclass == fc_oeclass)
			fc_pathkey = fc_opathkey;
		else
			fc_pathkey = make_canonical_pathkey(fc_root,
											 fc_ieclass,
											 fc_opathkey->pk_opfamily,
											 fc_opathkey->pk_strategy,
											 fc_opathkey->pk_nulls_first);

		/*
		 * 不要生成冗余的路径键（如果多个
		 * mergeclauses 引用相同的 EC，这可能会发生）。因为我们这样做，输出
		 * 路径键列表不一定像 mergeclauses 那样有序，这
		 * 给 create_mergejoin_plan() 带来了复杂性。但如果我们不这样做，
		 * 我们将拥有一个非规范的排序键列表，这将是不好的；原因之一，
		 * 它肯定不会与输入关系的任何可用排序顺序匹配。
		 */
		if (!fc_pathkey_is_redundant(fc_pathkey, fc_pathkeys))
			fc_pathkeys = lappend(fc_pathkeys, fc_pathkey);
	}

	return fc_pathkeys;
}

/*
 * trim_mergeclauses_for_inner_pathkeys
 *	  此例程修剪 mergeclauses 列表，仅包括那些与连接的内部关系
 *	  的指定排序方式相符的条目。
 *
 * 'mergeclauses' 是与要形成的连接关系的 mergejoin 子句的 RestrictInfos 列表，
 *		 按当前考虑的连接外侧的排序方式已知的顺序。
 * 'pathkeys' 是一个显示内部关系路径排序的路径键列表；
 *		 它应该等于或是对 make_inner_pathkeys_for_merge 的结果进行的截断。
 *
 * 我们返回的将是给定 mergeclauses 列表的前缀。
 *
 * 我们需要这个逻辑，因为 make_inner_pathkeys_for_merge 的结果不一定
 * 与 mergeclauses 的顺序相同。这意味着，如果我们
 * 考虑到一个内部关系路径键列表，它是该结果的截断，
 * 即使它们与一个幸存的内部路径键匹配，我们可能需要放弃
 * mergeclauses。这发生在它们位于与一个已移除的内部路径键匹配的 mergeclause 右侧时。
 *
 * mergeclauses 必须标记（通过 outer_is_left）以表明每个子句的哪一侧
 * 与当前的外部路径相关联。（见 select_mergejoin_clauses()）
 */
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *fc_root,
									 List *fc_mergeclauses,
									 List *fc_pathkeys)
{
	List	   *fc_new_mergeclauses = NIL;
	PathKey    *fc_pathkey;
	EquivalenceClass *fc_pathkey_ec;
	bool		fc_matched_pathkey;
	ListCell   *fc_lip;
	ListCell   *fc_i;

	/* 没有路径键 => 没有 mergeclauses（尽管我们不期望这种情况） */
	if (fc_pathkeys == NIL)
		return NIL;
	/* 初始化以考虑第一个路径键 */
	fc_lip = list_head(fc_pathkeys);
	fc_pathkey = (PathKey *) lfirst(fc_lip);
	fc_pathkey_ec = fc_pathkey->pk_eclass;
	fc_lip = lnext(fc_pathkeys, fc_lip);
	fc_matched_pathkey = false;

	/* 扫描 mergeclauses 看我们能使用多少 */
	foreach(fc_i, fc_mergeclauses)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_i);
		EquivalenceClass *fc_clause_ec;

		/* 假设我们不需要在这里再次执行 update_mergeclause_eclasses */

		/* 检查子句的内部关系 EC 是否与当前路径键匹配 */
		fc_clause_ec = fc_rinfo->outer_is_left ?
			fc_rinfo->right_ec : fc_rinfo->left_ec;

		/* 如果我们没有匹配，尝试前进到下一个路径键 */
		if (fc_clause_ec != fc_pathkey_ec)
		{
			/* 如果我们没有与此内部路径键匹配的子句，必须停止 */
			if (!fc_matched_pathkey)
				break;

			/* 前进到下一个内部路径键（如果有） */
			if (fc_lip == NULL)
				break;
			fc_pathkey = (PathKey *) lfirst(fc_lip);
			fc_pathkey_ec = fc_pathkey->pk_eclass;
			fc_lip = lnext(fc_pathkeys, fc_lip);
			fc_matched_pathkey = false;
		}

		/* 如果 mergeclause 与当前内部路径键匹配，我们可以使用它 */
		if (fc_clause_ec == fc_pathkey_ec)
		{
			fc_new_mergeclauses = lappend(fc_new_mergeclauses, fc_rinfo);
			fc_matched_pathkey = true;
		}
		else
		{
			/* 否则，没有希望再添加任何 mergeclauses */
			break;
		}
	}

	return fc_new_mergeclauses;
}


/****************************************************************************
 *		路径键有用性检查
 *
 * 我们只想记住路径的路径键中有潜在用途的数量，
 * 无论是用于后续 mergejoins，还是用于满足查询请求的输出排序。
 * 这确保了 add_path() 不会认为路径有一个有用的不同排序，
 * 除非它确实是有用的。这些例程检查给定路径键的有用性。
 ****************************************************************************/


/*
 * pathkeys_useful_for_merging
 *		计算在给定关系上可能有用的路径键数量，用于合并连接
 *
 * 我们认为一个路径键在潜在上是有用的，如果它对应于任何连接条件任一侧的合并排序。 这可能过于乐观，因为需要不同其他关系的连接条件可能不会同时可用，但试图精确可能会带来更多麻烦而不值得。
 *
 * 为了避免考虑合并连接路径数量的加倍，我们希望对于任何给定的目标列，仅考虑两个扫描方向（升序或降序）中的一个作为合并的有用方向。 这个选择是随意的，除非某个方向恰好与 ORDER BY 键匹配，在这种情况下应该优先选择该方向，希望避免最终的排序步骤。 right_merge_direction() 实现了这一启发式方法。
 */
static int fc_pathkeys_useful_for_merging(PlannerInfo *fc_root, RelOptInfo *fc_rel, List *fc_pathkeys)
{
	int			fc_useful = 0;
	ListCell   *fc_i;

	foreach(fc_i, fc_pathkeys)
	{
		PathKey    *fc_pathkey = (PathKey *) lfirst(fc_i);
		bool		fc_matched = false;
		ListCell   *fc_j;

		/* 如果是“错误”的方向，则不适合合并 */
		if (!fc_right_merge_direction(fc_root, fc_pathkey))
			break;

		/*
		 * 首先查看路径键的等价类，以查看是否有任何成员尚未与该关系连接。 如果有，肯定可以使用它们生成合并连接条件。
		 */
		if (fc_rel->has_eclass_joins &&
			eclass_useful_for_merging(fc_root, fc_pathkey->pk_eclass, fc_rel))
			fc_matched = true;
		else
		{
			/*
			 * 否则搜索关系的连接信息列表，其中包含不可从等价类推导出的连接条件，但仍然可能是合并连接的。
			 */
			foreach(fc_j, fc_rel->joininfo)
			{
				RestrictInfo *fc_restrictinfo = (RestrictInfo *) lfirst(fc_j);

				if (fc_restrictinfo->mergeopfamilies == NIL)
					continue;
				update_mergeclause_eclasses(fc_root, fc_restrictinfo);

				if (fc_pathkey->pk_eclass == fc_restrictinfo->left_ec ||
					fc_pathkey->pk_eclass == fc_restrictinfo->right_ec)
				{
					fc_matched = true;
					break;
				}
			}
		}

		/*
		 * 如果未找到合并子句，我们就完成了——路径键中的任何额外
		 * 排序键位置都是无用的。（但是如果至少找到了一个合并子句，我们仍然可以合并连接。）
		 */
		if (fc_matched)
			fc_useful++;
		else
			break;
	}

	return fc_useful;
}

/*
 * right_merge_direction
 *		检查路径键是否体现了合并其目标列的首选排序方向。
 */
static bool fc_right_merge_direction(PlannerInfo *fc_root, PathKey *fc_pathkey)
{
	ListCell   *fc_l;

	foreach(fc_l, fc_root->query_pathkeys)
	{
		PathKey    *fc_query_pathkey = (PathKey *) lfirst(fc_l);

		if (fc_pathkey->pk_eclass == fc_query_pathkey->pk_eclass &&
			fc_pathkey->pk_opfamily == fc_query_pathkey->pk_opfamily)
		{
			/*
			 * 找到了匹配的查询排序列。 如果方向匹配，则优先选择此路径键的方向。 请注意，我们忽略 pk_nulls_first，这意味着可能仍然需要排序……但我们仍然希望优先选择两个可能方向中的一个，而我们可以使用这个方向。
			 */
			return (fc_pathkey->pk_strategy == fc_query_pathkey->pk_strategy);
		}
	}

	/* 如果没有匹配的 ORDER BY 请求，优先选择 ASC 方向 */
	return (fc_pathkey->pk_strategy == BTLessStrategyNumber);
}

/*
 * pathkeys_useful_for_ordering
 *		计算对满足查询请求的输出排序有用的路径键数量。
 *
 * 由于我们有增量排序的可能性，键的前缀列表可能有助于提高请求排序的性能。 因此，如果未找到有价值的键，则返回0，或者返回列表与请求排序共享的前导键的数量。
 */
static int fc_pathkeys_useful_for_ordering(PlannerInfo *fc_root, List *fc_pathkeys)
{
	int			fc_n_common_pathkeys;

	if (fc_root->query_pathkeys == NIL)
		return 0;				/* 未请求特殊排序 */

	if (fc_pathkeys == NIL)
		return 0;				/* 无序路径 */

	(void) pathkeys_count_contained_in(fc_root->query_pathkeys, fc_pathkeys,
									   &fc_n_common_pathkeys);

	return fc_n_common_pathkeys;
}

/*
 * truncate_useless_pathkeys
 *		将给定的路径键列表缩短为仅有用的路径键。
 */
List * truncate_useless_pathkeys(PlannerInfo *fc_root,
						  RelOptInfo *fc_rel,
						  List *fc_pathkeys)
{
	int			fc_nuseful;
	int			fc_nuseful2;

	fc_nuseful = fc_pathkeys_useful_for_merging(fc_root, fc_rel, fc_pathkeys);
	fc_nuseful2 = fc_pathkeys_useful_for_ordering(fc_root, fc_pathkeys);
	if (fc_nuseful2 > fc_nuseful)
		fc_nuseful = fc_nuseful2;

	/*
	 * 注意：不安全修改输入列表，但如果我们不打算实际更改它，可以避免复制列表
	 */
	if (fc_nuseful == 0)
		return NIL;
	else if (fc_nuseful == list_length(fc_pathkeys))
		return fc_pathkeys;
	else
		return list_truncate(list_copy(fc_pathkeys), fc_nuseful);
}

/*
 * has_useful_pathkeys
 *		检测指定关系是否可能有根据 truncate_useless_pathkeys() 而有用的路径键。
 *
 * 这是一个廉价的测试，让我们在非常简单的查询中跳过构建路径键的步骤。 在实际上没有任何可用路径键时，返回“true”的方向上出错是可以的，但在另一个方向上出错则是错误的——因此要与上述例程保持同步！
 *
 * 我们可以使测试更复杂，例如检查是否有任何连接子句实际上可以进行合并连接，但这可能不会足够频繁地赢得额外的周期。 然而，没有连接也没有排序的查询相对常见，因此这项工作似乎是值得的。
 */
bool has_useful_pathkeys(PlannerInfo *fc_root, RelOptInfo *fc_rel)
{
	if (fc_rel->joininfo != NIL || fc_rel->has_eclass_joins)
		return true;			/* 可能能够使用路径键进行合并 */
	if (fc_root->query_pathkeys != NIL)
		return true;			/* 可能能够使用它们进行排序 */
	return false;				/* 确实无用 */
}
